home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr26 / netprog.zip / NETPROG.TAR / lib / rtt.c < prev    next >
C/C++ Source or Header  |  1989-12-17  |  6KB  |  226 lines
  1. /*
  2.  * Timer routines for round-trip timing of datagrams.
  3.  *
  4.  *    rtt_init()    Called to initialize everything for a given
  5.  *            "connection."
  6.  *    rtt_newpack()    Called before each new packet is transmitted on
  7.  *            a "connection."  Initializes retransmit counter to 0.
  8.  *    rtt_start()    Called before each packet either transmitted or
  9.  *            retransmitted.  Calculates the timeout value for
  10.  *            the packet and starts the timer to calculate the RTT.
  11.  *    rtt_stop()    Called after a packet has been received.
  12.  *    rtt_timeout()    Called after a timeout has occurred.  Tells you
  13.  *            if you should retransmit again, or give up.
  14.  *
  15.  * The difference between rtt_init() and rtt_newpack() is that the former
  16.  * knows nothing about the "connection," while the latter makes use of
  17.  * previous RTT information for a given "connection."
  18.  */
  19.  
  20. #include    <sys/types.h>
  21. #include    "rtt.h"
  22.  
  23. int    exp_backoff[ RTT_MAXNREXMT + 1 ] =
  24.         { 1, 2, 4, 8, 16 };
  25.     /* indexed by rtt_nrexmt: 0, 1, 2, ..., RTT_MAXNREXMT.
  26.        [0] entry (==1) is not used;
  27.        [1] entry (==2) is used the second time a packet is sent; ... */
  28.  
  29. int    rtt_d_flag = 0;        /* can be set nonzero by caller */
  30.  
  31. /*
  32.  * Initialize an RTT structure.
  33.  * This function is called before the first packet is transmitted.
  34.  */
  35.  
  36. rtt_init(ptr)
  37. register struct rtt_struct    *ptr;    /* ptr to caller's structure */
  38. {
  39.     ptr->rtt_rtt    = 0;
  40.     ptr->rtt_srtt   = 0;
  41.     ptr->rtt_rttdev = 1.5;
  42.         /* first timeout at (srtt + (2 * rttdev)) = 3 seconds */
  43.     ptr->rtt_nxtrto = 0;
  44. }
  45.  
  46. /*
  47.  * Initialize the retransmit counter before a packet is transmitted
  48.  * the first time.
  49.  */
  50.  
  51. rtt_newpack(ptr)
  52. register struct rtt_struct    *ptr;    /* ptr to caller's structure */
  53. {
  54.     ptr->rtt_nrexmt = 0;
  55. }
  56.  
  57. /*
  58.  * Start our RTT timer.
  59.  * This should be called right before the alarm() call before a packet
  60.  * is received.  We calculate the integer alarm() value to use for the
  61.  * timeout (RTO) and return it as the value of the function.
  62.  */
  63.  
  64. int
  65. rtt_start(ptr)
  66. register struct rtt_struct    *ptr;    /* ptr to caller's structure */
  67. {
  68.     register int    rexmt;
  69.  
  70.     if (ptr->rtt_nrexmt > 0) {
  71.         /*
  72.          * This is a retransmission.  No need to obtain the
  73.          * starting time, as we won't use the RTT for anything.
  74.          * Just apply the exponential back off and return.
  75.          */
  76.  
  77.         ptr->rtt_currto *= exp_backoff[ ptr->rtt_nrexmt ];
  78.         return(ptr->rtt_currto);
  79.     }
  80.  
  81. #ifdef BSD
  82.     if (gettimeofday(&ptr->time_start, (struct timezone *) 0) < 0)
  83.         err_sys("rtt_start: gettimeofday() error");
  84. #endif
  85.  
  86. #ifdef SYS5
  87.     if ( (ptr->time_start = times(&ptr->tms_start)) == -1)
  88.         err_sys("rtt_start: times() error");
  89. #endif
  90.  
  91.     if (ptr->rtt_nxtrto > 0) {
  92.         /*
  93.          * This is the first transmission of a packet *and* the
  94.          * last packet had to be retransmitted.  Therefore, we'll
  95.          * use the final RTO for the previous packet as the
  96.          * starting RTO for this packet.  If that RTO is OK for
  97.          * this packet, then we'll start updating the RTT estimators.
  98.          */
  99.  
  100.         ptr->rtt_currto = ptr->rtt_nxtrto;
  101.         ptr->rtt_nxtrto = 0;
  102.         return(ptr->rtt_currto);
  103.     }
  104.  
  105.     /*
  106.      * Calculate the timeout value based on current estimators:
  107.      *    smoothed RTT plus twice the deviation.
  108.      */
  109.  
  110.     rexmt = (int) (ptr->rtt_srtt + (2.0 * ptr->rtt_rttdev) + 0.5);
  111.     if (rexmt < RTT_RXTMIN)
  112.         rexmt = RTT_RXTMIN;
  113.     else if (rexmt > RTT_RXTMAX)
  114.         rexmt = RTT_RXTMAX;
  115.     return( ptr->rtt_currto = rexmt );
  116. }
  117.  
  118. /*
  119.  * A response was received.
  120.  * Stop the timer and update the appropriate values in the structure
  121.  * based on this packet's RTT.  We calculate the RTT, then update the
  122.  * smoothed RTT and the RTT variance.
  123.  * This function should be called right after turning off the
  124.  * timer with alarm(0), or right after a timeout occurs.
  125.  */
  126.  
  127. rtt_stop(ptr)
  128. register struct rtt_struct    *ptr;    /* ptr to caller's structure */
  129. {
  130.     double        start, stop, err;
  131.  
  132.     if (ptr->rtt_nrexmt > 0) {
  133.         /*
  134.          * The response was for a packet that has been retransmitted.
  135.          * We don't know which transmission the response corresponds to.
  136.          * We didn't record the start time in rtt_start(), so there's
  137.          * no need to record the stop time here.  We also don't
  138.          * update our estimators.
  139.          * We do, however, save the RTO corresponding to this
  140.          * response, and it'll be used for the next packet.
  141.          */
  142.  
  143.         ptr->rtt_nxtrto = ptr->rtt_currto;
  144.         return;
  145.     }
  146.     ptr->rtt_nxtrto = 0;        /* for next call to rtt_start() */
  147.  
  148. #ifdef BSD
  149.     if (gettimeofday(&ptr->time_stop, (struct timezone *) 0) < 0)
  150.         err_sys("rtt_stop: gettimeofday() error");
  151.     start = ((double) ptr->time_start.tv_sec) * 1000000.0
  152.                 + ptr->time_start.tv_usec;
  153.     stop = ((double) ptr->time_stop.tv_sec) * 1000000.0
  154.                 + ptr->time_stop.tv_usec;
  155.     ptr->rtt_rtt = (stop - start) / 1000000.0;    /* in seconds */
  156. #endif
  157.  
  158. #ifdef SYS5
  159.     if ( (ptr->time_stop = times(&ptr->tms_stop)) == -1)
  160.         err_sys("t_stop: times() error");
  161.     ptr->rtt_rtt = (double) (ptr->time_stop - ptr->time_start)
  162.                 / (double) TICKS;    /* in seconds */
  163. #endif
  164.  
  165.     /*
  166.      * Update our estimators of RTT and mean deviation of RTT.
  167.      * See Jacobson's SIGCOMM '88 paper, Appendix A, for the details.
  168.      * This appendix also contains a fixed-point, integer implementation
  169.      * (that is actually used in all the post-4.3 TCP code).
  170.      * We'll use floating point here for simplicity.
  171.      *
  172.      * First
  173.      *    err = (rtt - old_srtt) = difference between this measured value
  174.      *                 and current estimator.
  175.      * and
  176.      *    new_srtt = old_srtt*7/8 + rtt/8.
  177.      * Then
  178.      *    new_srtt = old_srtt + err/8.
  179.      *
  180.      * Also
  181.      *    new_rttdev = old_rttdev + (|err| - old_rttdev)/4.
  182.      */
  183.  
  184.     err = ptr->rtt_rtt - ptr->rtt_srtt;
  185.     ptr->rtt_srtt += err / 8;
  186.  
  187.     if (err < 0.0)
  188.         err = -err;    /* |err| */
  189.  
  190.     ptr->rtt_rttdev += (err - ptr->rtt_rttdev) / 4;
  191. }
  192.  
  193. /*
  194.  * A timeout has occurred.
  195.  * This function should be called right after the timeout alarm occurs.
  196.  * Return -1 if it's time to give up, else return 0.
  197.  */
  198.  
  199. int
  200. rtt_timeout(ptr)
  201. register struct rtt_struct    *ptr;    /* ptr to caller's structure */
  202. {
  203.     rtt_stop(ptr);
  204.  
  205.     if (++ptr->rtt_nrexmt > RTT_MAXNREXMT)
  206.         return(-1);        /* time to give up for this packet */
  207.  
  208.     return(0);
  209. }
  210.  
  211. /*
  212.  * Print debugging information on stderr, if the "rtt_d_flag" is nonzero.
  213.  */
  214.  
  215. rtt_debug(ptr)
  216. register struct rtt_struct    *ptr;    /* ptr to caller's structure */
  217. {
  218.     if (rtt_d_flag == 0)
  219.         return;
  220.  
  221.     fprintf(stderr, "rtt = %.5f, srtt = %.3f, rttdev = %.3f, currto = %d\n",
  222.             ptr->rtt_rtt, ptr->rtt_srtt, ptr->rtt_rttdev,
  223.             ptr->rtt_currto);
  224.     fflush(stderr);
  225. }
  226.